﻿//class Solution
//{
//public:
//	double myPow(double x, int n)
//	{
//		return n < 0 ? 1.0 / pow(x, -(long long)n) : pow(x, n);
//	}
//	double pow(double x, long long n)
//	{
//		if (n == 0) return 1.0;
//		double tmp = pow(x, n / 2);
//		return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
//	}
//};



//class Solution
//{
//	public TreeNode pruneTree(TreeNode root)
//	{
//		if (root == null) return null;
//		root.left = pruneTree(root.left);
//		root.right = pruneTree(root.right);
//		if (root.left == null && root.right == null && root.val == 0)
//			root = null;
//		return root;
//	}
//}




//class Solution
//{
//	int m, n;
//	int dx[4] = { 0, 0, 1, -1 };
//	int dy[4] = { 1, -1, 0, 0 };
//public:
//	vector<vector<int>> pacificAtlantic(vector<vector<int>>& h)
//	{
//		m = h.size(), n = h[0].size();
//		vector<vector<bool>> pac(m, vector<bool>(n));
//		vector<vector<bool>> atl(m, vector<bool>(n));
//		// 1. 先处理 pac 洋
//		for (int j = 0; j < n; j++) dfs(h, 0, j, pac);
//		for (int i = 0; i < m; i++) dfs(h, i, 0, pac);
//		// 2. 处理 atl 洋
//		for (int i = 0; i < m; i++) dfs(h, i, n - 1, atl);
//		for (int j = 0; j < n; j++) dfs(h, m - 1, j, atl);
//		vector<vector<int>> ret;
//		for (int i = 0; i < m; i++)
//			for (int j = 0; j < n; j++)
//				if (pac[i][j] && atl[i][j])
//					ret.push_back({ i, j });
//		return ret;
//	}
//	void dfs(vector<vector<int>>& h, int i, int j, vector<vector<bool>>& vis)
//	{
//		vis[i][j] = true;
//		for (int k = 0; k < 4; k++)
//		{
//			int x = i + dx[k], y = j + dy[k];
//			if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && h[x][y] >=
//				h[i][j])
//				dfs(h, x, y, vis);
//		}
//	}
//};



class Solution
{
	int dx[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };
	int dy[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
	int m, n;
public:
	vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>&
		click)
	{
		m = board.size(), n = board[0].size();
		int x = click[0], y = click[1];
		if (board[x][y] == 'M') 
		{
			board[x][y] = 'X';
			return board;
		}
		dfs(board, x, y);
		return board;
	}
	void dfs(vector<vector<char>>& board, int i, int j)
	{
		// 统计⼀下周围的地雷个数
		int count = 0;
		for (int k = 0; k < 8; k++)
		{
			int x = i + dx[k], y = j + dy[k];
			if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M')
			{
				count++;
			}
		}
		if (count) // 周围有地雷
		{
			board[i][j] = count + '0';
			return;
		}
		else // 周围没有地雷
		{
			board[i][j] = 'B';
			for (int k = 0; k < 8; k++)
			{
				int x = i + dx[k], y = j + dy[k];
				if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E')
				{
					dfs(board, x, y);
				}
			}
		}
	}
};